Bentley OpenFlows HAMMER CONNECT Edition 帮助

竞争遗传算法

遗传算法的工作机制派生自以下简单假设(Holland,1975 年):最佳解将在包含相对较高比例的优良解的解域中找到。一组表示优良解的字符串在位值方面具有一定相似性。例如,3 位二进制字符串 001、111、101 和 011 具有共同的相似性模板 **1,其中星号 (*) 表示无关符号,其值为 1 或 0。这四个字符串表示四个优良解,并构成了适合度值 10、12、11 和 11,适合度函数为:

其中 x1、x2 和 x3 从左到右直接采用位值作为整数。一般而言,贡献高于平均值的适合度的简要相似性模板称为构建基块。构建基块通常包含在表示特定问题的部分解的短字符串中。因此,搜索优良解可揭示匹配的短字符串并将其并置,这基本上指定了优良解域,并最终使搜索找到最佳解。

Goldberg 等人致力于提高遗传算法 (Genetic Algorithm, GA) 发现和交换构建基块的能力,从而于 1989 年开发了混合遗传算法作为竞争遗传算法范式之一。第一代混合遗传算法会显式初始化所需长度为 k 的所有短字符串,其中 k 称为短字符串定义的构建基块的阶。对于二进制字符串表示形式,k 阶构建基块的所有组合对 l 位问题要求多个长度为 k 的初始短字符串:

例如,通过完全枚举 40 位问题的 4 阶构建基块,短字符串的初始群体大小超过一百万。这使得无法将第一代混合遗传算法应用于大规模优化问题。此瓶颈已通过将构建基块筛选过程引入到混合遗传算法中(Goldberg 等人,1993 年)而得以克服。该筛选过程可加速搜索过程,称为快速混合遗传算法。

快速混合遗传算法在两个嵌套循环(一个外部循环和一个内部循环)中模拟强大的遗传进化过程。外部循环的每个周期(表示为年代)都会调用初始化阶段,以及包含构建基块筛选阶段和并置阶段的内部循环。与简单遗传算法一样,混合遗传算法初始化会创建一个包含随机个体的群体。群体大小必须足够大才能确保所有可能的构建基块都存在。随后将应用构建基块筛选过程,以选择更匹配的短字符串并减小字符串长度。该过程的工作方式类似于过滤器,以便删除不属于构建基块的不良基因,从而使群体包含较高比例的具有良好基因的短字符串。筛选过程将继续进行,直到字符串总长度缩短至所需的长度 k。最后,并置阶段会紧接着进行,以生成新字符串。在此阶段,处理的构建基块会进行合并和交换,以通过应用选择算子和再生算子来产生后代。当达到最大代数时,并置阶段将终止,一个年代迭代周期此时便告完成。包含所需构建基块的短字符串的长度通常指定为与一个年代相同,从一个年代开始演变到最大年代数。因此,首选短字符串的长度会随着外部迭代而增加。换言之,混合遗传算法会使解演变,短字符串的长度从一个字符开始演变到所需的最大长度。这使混合遗传算法能够模拟自然和生物进化过程,即简单或单细胞生物体进化成更复杂、智力更高的生物体的过程。Goldberg 等人(1989 年和 1993 年)已公布混合遗传算法的详细分析和计算过程。